package chapter01;

import org.w3c.dom.ls.LSOutput;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class PermuteUnique47 {
    /**
     * 回溯+剪枝
     * 排序是剪枝的前提 出现重复的原因是 同一层出现重复元素
     * 对每一个位置元素都标记是否被使用过 因此循环从[0~length-1] 选择没有被使用过的元素进行全排列
     * 排除重复元素的方法是 遇到数组中当前元素与前一个元素相同并且前一个元素未被使用过时应当剪枝
     * 理解：虽然[i]==[i-1]但是[i-1]与[i]可能处于同一层或者[i-1]与[i]是上下层
     *      如果是上下层那么不需要剪枝  如果是处于同一层需要剪枝
     *      如果是处于同一层 因为是从[0~length-1]开始尝试 [i-1]一定在[i]之前进行尝试
     *      如果[i-1]标记为false说明在[i]尝试前[i-1]已经尝试过并重新恢复为未使用状态
     * 1) [i]==[i-1]&&[i-1]&&used[i-1]==false
     *      continue
     * 2) used[i]==true
     *      每次都是从[0~length-1]开始尝试 已经使用过的元素不再使用
     *      continue
     */
    List<List<Integer>> list=new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        boolean[] used=new boolean[nums.length];
        List<Integer> path=new ArrayList<>();
        dfs(nums,0,path,used);
        return list;
    }

    public void dfs(int[] nums,int pos,List<Integer> path,boolean[] used){
        if(path.size()==nums.length){
            list.add(new ArrayList<>(path));
        }
        for(int i=0;i<nums.length;i++){
            if(used[i]){
                continue;
            }
            if(i>0&&nums[i]==nums[i-1]&&used[i-1]==false){
                continue;
            }
            path.add(nums[i]);
            used[i]=true;
            dfs(nums,pos+1,path,used);
            used[i]=false;
            path.remove(pos);
        }
    }
}
